Madonna xuất hiện lần đầu tiên trên chương trình Letterman khi cô là một khách mời vào năm 1988 với diễn viên hài Sandra Bernhard.[4] Sau đó, cô đã tiếp tục trở thành khách mời của tập phát sóng ngày 31 tháng 3 năm 1994 trong The Late Show, đánh dấu lần đầu tiên cô xuất hiện trên truyền hình Mỹ năm đó.Letterman đã giới thiệu về Madonna trước khi cô xuất hiện trong trường quay:

Vị khách đầu tiên của chúng ta tối nay là một trong những ngôi sao lớn của thế giới, trong 10 năm qua cô đã bán được hơn 80 triệu album, xuất hiện trong rất nhiều bộ phim và quan hệ với một số tên tuổi lớn trong ngành giải trí.[5]

Paul Shaffer sau đó đã phản ứng lại rằng "cô ấy là khách mời của anh mà!... Thôi nào, cô ấy là khách mời của anh đấy!", Letterman tiếp tục trả lời rằng, "mọi thứ đều ổn cả, cứ thư giãn, được chứ?". Madonna sau đó đã xuất hiện tại sân khấu chính trong nền nhạc của bài hát "Holiday" khi trong tay cô đang cầm chiếc quần lót của mình, bắt Letterman phải ngửi chúng trong buổi phỏng vấn. Sau khi cô xuất hiện, Letterman đã hỏi ý kiến cô về việc hôn một khán giả nam; nhưng Madonna đã từ chối. Letterman sau đó đã trêu chọc về sự từ chối của cô và chuyển sang một chủ đề khác, nhưng cô đã nhanh chóng đáp lại rằng, "Incidentally, you are a sick fuck. I don't know why I get so much shit." (tạm dịch: "Tình cờ, anh là một thằng khốn bệnh hoạn. Tôi không hiểu sao mình lại nhận nhiều thứ quái gở thế này.")

Letterman sau đó đã hỏi về cuộc sống đời tư của cô, chuyện cô quan hệ với một vài cầu thủ NBA. Madonna sau đó đã trả lời anh với một vài câu nói bóng gió rằng "cái micro [trên cao] thật là dài"; Letterman sau đó đã tiếp tục hỏi cô về tình bạn của mình với Charles Barkley. Nhưng khi anh chuyển chủ đề khác và hỏi cô về nhẫn xỏ mũi một cách mơ hồ rằng, "Did it hurt when you had that thing put in, uh, put in your nose?" (tạm dịch: "Bạn có bị đau khi có cái thứ ở trong, ờ, ở trong mũi bạn chứ?"), Madonna sau đó đã cười và nói rằng "I thought you were going to ask me if it hurt something else..." (tạm dịch: "Tôi tưởng anh sẽ hỏi tôi có bị đau ở chỗ khác...") và nhận được những lời than vãn của khán giả trong phòng quay.

Trước khi đến phần quảng cáo (Madonna đã từ chối việc phát quảng cáo, cho rằng cô muốn "phá vỡ luật lệ" của truyền hình Mỹ), cô đã hỏi Letterman rằng có phải anh đang đội một bộ tóc giả hay không; sau đó, Letterman đã không bỏ lỡ cơ hội của mình, trêu chọc mái tóc ngắn được đánh bóng của cô là một chiếc mũ bơi.

Sau phần quảng cáo, Letterman mời Madonna hút xì-gà, nhưng cô lại cho rằng anh đã thay đổi sau lần gặp trước, rằng anh không hề "tuyệt vời" hay thách thức khác mời của mình. Letterman sau đó hỏi việc gì thực sự làm phiền cô trong chương trình; Madonna đã đáp lại rằng cô rất tức giận khi anh luôn lấy đời sống tình dục của cô ra để trêu chọc thường xuyên.

Khi Madonna tiếp tục chửi thề, đạo diễn đã quay một cặp vợ chồng lớn tuổi từ Appleton, Wisconsin khi cả hai đều bị sốc bởi ngôn ngữ của Madonna. Sau đó, chương trình đã trình chiếu đoạn video khi Madonna đang đạp xe khỏa thân.

Sau phần quảng cáo thứ hai, Madonna hỏi Letterman rằng anh có bao giờ đi tiểu trong khi tắm vòi hoa sen, cho đó là một chất khử trùng cho chân của các vận động viên.

Trong buổi phỏng vấn, Letterman có hỏi Madonna rằng liệu cô có bạn trai chưa ("Are you currently interested in someone?"; tạm dịch: "Hiện tại bạn có để ý ai không nhỉ?"). Cô trả lời rằng là có, nhưng đến khi được hỏi tên của người đàn ông ấy thì cô đáp lại rằng là "Dave." Letterman sau đó đã "đánh trống lãng" bằng cách hỏi cô về David Dinkins, cựu thị trưởng của New York.

Gần khúc cuối của buổi trò chuyện, cô đồng thời cũng hỏi Letterman rằng anh có hút "Endo", tiếng lóng ngụ ý cần sa. Tỏ vẻ không thoải mái, anh nói với cô rằng anh không hề biết nó là gì; Madonna lại cho rằng anh đang nói dối, khiến Letterman diễn tả lại hành động của Johnny Carson khi gặp những câu trả lời gây bối rối.

Khi Madonna từ chối rời khỏi trường quay, mọi khán giả đã chế giễu cô, trong đó có một người la lên "cút đi". Nhưng cô vẫn không hề rời khỏi ghế ngồi của mình; thay vào đó, chương trình lại chiếu một đoạn quảng cáo thứ ba, sau khi Madonna rời bỏ. Letterman nói đùa rằng, "Coming up in the next half hour, Mother Teresa is going to drop by." (tạm dịch: "Nửa tiếng nữa, Mẹ Teresa sẽ đến đây ghé thăm.") Sau đó anh nhìn vào thẻ thông tin của mình và giễu cợt rằng, "Oh, I see we've been canceled, there is no show tomorrow night." (tạm dịch: "Ôi, chúng ta đã bị hoãn rồi, không còn chương trình nào tối mai nữa.")

Khách mời tiếp theo, nhà vô địch Đóng bao tạp hóa của Hoa Kỳ năm ấy, đã được lên lịch xuất hiện trên chương trình tối hôm ấy, nhưng phân đoạn của anh đã bị cắt vì Madonna từ chối rời khỏi sân khấu khi buổi phỏng vấn kết thúc. Cuối cùng, Counting Crows đã kết thúc chương trình bằng bài "Round Here".